package pro.softzhang.algo.lc0;

/**
 *
 */
public class LC67_AddBinary {
    public static void main(String[] args) {
        String a = "11";
        String b = "11";
        System.out.println(new LC67_AddBinary().addBinary2(a, b));
    }

    public String addBinary(String a, String b) {
        int ap = a.length() - 1, bp = b.length() - 1, carry = 0;
        // 优化sb占用
        StringBuilder sb = new StringBuilder(ap >= bp ? ap + 2 : bp + 2);

        while (ap >= 0 || bp >= 0) {
            int na = ap < 0 ? 0 : (a.charAt(ap) == '0' ? 0 : 1);
            int nb = bp < 0 ? 0 : (b.charAt(bp) == '0' ? 0 : 1);
            int sum = na + nb + carry, diff = sum - 2;
            if(diff >= 0) {
                sb.append(diff);
                carry = 1;
            } else {
                sb.append(sum);
                carry = 0;
            }

            ap--;
            bp--;
        }

        if(carry == 1) {
            sb.append(carry);
        }

        return sb.reverse().toString();
    }

    /**
     * 第二次做
     * @param a
     * @param b
     * @return
     */
    public String addBinary2(String a, String b) {
        int ap = a.length() - 1, bp = b.length() - 1, carry = 0;
        StringBuilder sb = new StringBuilder(Math.max(ap, bp) + 2);
        while (ap >= 0 || bp >= 0) {
            int ic = (ap < 0 || a.charAt(ap--) == '0') ? 0 : 1;
            int ib = (bp < 0 || b.charAt(bp--) == '0') ? 0 : 1;
            int sum = ic + ib + carry;
            carry = sum >= 2 ? 1 : 0;
            sb.append(carry == 1 ? sum - 2 : sum);
        }

        // 最后末尾
        if(carry == 1) {
            sb.append(carry);
        }

        return sb.reverse().toString();
    }
}
